import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    char[] s;
    int[][] mem;

    public int numDupDigitsAtMostN(int n) {
        //先把n转换为字符串
        //之后转换为数组
        s = Integer.toString(n).toCharArray();
        int len = s.length;
        return 1;
    }
}

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) {
        int a = 0, c = 1;
        String ss = "abac";
        ss.length();
        System.out.println();
    }

    public static void main994(String[] args) {
        String s = "ab1    ";
        if (Character.isDigit(s.charAt(2))) {
            System.out.println();
        }
        Deque<Character> que = new LinkedList<>();

    }

    public static void main6646(String[] args) {
        int[] nums = {1, 2, 3};
        add(nums);
        Arrays.sort(nums);
        for (int tmp : nums) {
            System.out.println(tmp);
        }
        System.out.println("一节半");

        System.out.println(Integer.MIN_VALUE);
    }

    public static void add(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            nums[i]++;
        }
    }

    public static void main666(String[] args) {
        int count = 0;
        int ret = 120;
        count += ret / 5;
        System.out.println(count);
        System.out.println();
    }

    public static void main333(String[] args) {
        String s = "0.0120";
        int u = 5;
        System.out.println(s.substring(u));
        System.out.println(s.length());
        System.out.println(s.substring(0, u));
        System.out.println(String.format("%s(%s)", s.substring(0, u), s.substring(u)));
        int a = 19;
        int b = 5;
        System.out.println(a / b);
    }

    public static void main14(String[] args) {
        String ret = "1.2.3.45.5  ";
        int a = 1;
        int c = 3;
        double d = (double) a / c;
        System.out.println(((Double) d).toString());
        Double f = 33.0;

        System.out.println(d);

    }

    public static void barrelSort(int[] nums) {
        int n = nums.length;
        int max = 0, min = 0;

        //找出最大最小值
        for (int i = 0; i < n; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }

        int size = (max - min) / n + 1;//获取桶的个数，至少保证有一个
        int count = (max - min) / size + 1;//得知每个桶中存取数据范围(相当于差值)

        List<Integer>[] barrel = new List[size];//初始化每个桶
        for (int i = 0; i < size; i++) {
            barrel[i] = new ArrayList<>();
        }

        //扫描一遍数组，把数放在对应的桶里面
        for (int i = 0; i < n; i++) {
            int index = (nums[i] - min) / size;//定位第几个桶
            barrel[index].add(nums[i]);
        }

        //对同种每个数据进行排序，这里使用快排
        for (int i = 0; i < size; i++) {
            barrel[i].sort(null);//默认就是升序排序，不需要使用比较器
        }

        //一次出桶
        int index = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < barrel[i].size(); j++) {
                nums[index++] = barrel[i].get(j);
            }
        }

    }

    public static void main12(String[] args) {
        int[] nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};
        barrelSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + "  ");
        }

    }


    public static void main44(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int a = 10;
        int b = 20;
        System.out.println(Math.abs(a - b));
    }


    public static void main6(String[] args) {
        Map<Integer, Integer> map = new HashMap();
        Stack<Integer> stack = new Stack<>();


    }

    public static void main5(String[] args) {
        List<TreeNode> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        list2.add(5);
        list2.add(2);
        list2.add(3);
        list1.add(list2);
        System.out.println(list1.get(0).get(0));

        list.add(1);
        list.add(2);
        list.add(3);
        Integer[] nums = list.toArray(new Integer[0]);
        System.out.println(list.get(0));

    }

    public static void main4(String[] args) {
        List<TreeNode> ret = new ArrayList<>();
        ret = bfs();
        System.out.println(ret);

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        System.out.println(queue.peek());
    }

    public static List<TreeNode> bfs() {
        return new ArrayList() {
            {
                add(null);
            }
        };
    }

    public static void main3(String[] args) {
        List<Integer>[] dp = new ArrayList[5 + 1];

        for (int i = 0; i < 6; i++) {
            dp[i] = new ArrayList<>();
        }

        dp[0].add(0);
    }

    public static void main2(String[] args) {
        Integer[] arry = {0, 1, 2};
        int[] diff = {85, 41, 57};
        Arrays.fill(arry, -1);
        int max = Integer.MAX_VALUE;
        System.out.println(max);
        Arrays.sort(arry, (a, b) -> (diff[a] - diff[b]));
        for (int x : arry) {
            System.out.print(x + " ");
        }


        Stack<Integer> stack = new Stack<>();

        System.out.println();
        System.out.println(1 << 0);

//        Integer a = 10;
//        Integer b = 6;
//        System.out.println(a.compareTo(b));
    }

    public static void main1(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("abc", map.getOrDefault("abc", 0) + 1);
        System.out.println(map.get("abc"));
        map.remove("abc");
        System.out.println("今天刷了5道题，还不错");

        List<Integer> list = new LinkedList<>();
        list.toString();

        System.out.println(map.size());
        map.containsKey("abc");
        System.out.println("今天真的在补课");
        System.out.println("爽！！！");
        System.out.println("明天解决所有问题！");
        System.out.println("一天两节课，三道题");
        System.out.println("摆烂了");
        String str = "abc";
        System.out.println("又白了");
        System.out.println("补了一节课");
        for (char tmp : str.toCharArray()) {
            System.out.println(tmp);
        }


        System.out.println("完了");
        System.out.println();
    }
}